package leetcode.editor.cn.q1_300.q100;

/**
 * 用每个峰值来将数组分割为 n 个区间，每个区间的最小值为 1，然后计算出的结果就是最少的糖果
 *
 * @author qidi
 * @date 2022-01-14 11:18:21
 */
class Q0135_Candy {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int candy(int[] ratings) {
            int n = ratings.length;
            if (n == 1) return 1;

            int i = 0;
            int left = 0;
            int[] candies = new int[n];

            while (i < n - 1) {
                if (ratings[i] <= ratings[i + 1]) {
                    // 趋势向上 left 为最低点
                    while (i < n) {
                        if (i < n - 1 && ratings[i] > ratings[i + 1] || i == n - 1) break;
                        i++;
                    }
                    candies[left] = 1;
                    for (int j = left; j < i; j++) {
                        if (ratings[j + 1] != ratings[j]) {
                            candies[j + 1] = candies[j] + 1;
                        } else {
                            candies[j + 1] = 1;
                        }
                    }
                    left = i;
                }
                if (i < n - 1 && ratings[i] >= ratings[i + 1]) {
                    // 趋势向下，left 为最高点
                    while (i < n) {
                        if (i < n - 1 && ratings[i] < ratings[i + 1] || i == n - 1) break;
                        i++;
                    }
                    candies[i] = 1;
                    for (int j = i - 1; j >= left; j--) {
                        int ca;
                        if (ratings[j] != ratings[j + 1]) {
                            ca = candies[j + 1] + 1;
                        } else {
                            ca = 1;
                        }
                        if (j == left) {
                            candies[j] = Math.max(candies[left], ca);
                        } else {
                            candies[j] = ca;
                        }
                    }
                    left = i;
                }
            }

            int ans = 0;

            for (int candy : candies) {
                ans += candy;
            }

            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0135_Candy().new Solution();
        System.out.println(solution.candy(new int[]{10, 10, 10, 10, 10, 10}));
        System.out.println(solution.candy(new int[]{1, 3, 4, 4, 5, 9, 2, 3, 8, 1, 3, 1}));
        System.out.println(solution.candy(new int[]{5, 8, 8, 2, 1, 3, 5, 4, 6, 7}));
        System.out.println(solution.candy(new int[]{3, 2, 1, 2, 3}));
        System.out.println(solution.candy(new int[]{1, 2, 3, 2, 1}));
    }
}